#include <bits/stdc++.h>

using namespace std;
typedef struct trieNode{
    bool over;
    string key,value;
    trieNode* nodes[26] = {nullptr};
    trieNode(){
        over = false;
        key = value = "";
    }
}trieNode,*trieTree;

class Trie{
    private:
    trieTree root;
    public:
    Trie(){
        root = new trieNode();
        root->over = false;
    }
    
    //插入单词
    bool insert(string key,string value){
        if(key == "" || key.length() == 0){
            return false;
        }
        trieTree node = root;
        trieTree tempNode;
        int len = key.length();
        for(int i = 0; i < len; ++i){
            if(key[i] - 'a' > 25 || key[i] - 'a' < 0){
                return false;
            }
            tempNode = node->nodes[key[i] - 'a'];
            if(tempNode == nullptr){
                tempNode = new trieNode();
                node->nodes[key[i] - 'a'] = tempNode;
            }
            node = tempNode;
        }
        if(!node->over){
            node->over = true;
            node->key = key;
            node->value = value;
            return true;
        }
        return false;
    }
    //模糊查找
    vector<trieTree> fuzzySearch(trieTree node,vector<trieTree> &v){
        if(node == nullptr){
            return v;
        }
        for(int i = 0; i < 26; ++i){
            trieTree tempNode = node->nodes[i];
            if(tempNode != nullptr && v.size() < 5)
            {
                if(tempNode->over){
                    v.push_back(tempNode);
                }
                fuzzySearch(tempNode, v);
            }
        }
        return v;
    }

    //查找单词
    vector<trieTree> search(string key){
        vector<trieTree> v;
        if(key == "" || key.length() == 0){
            return v;
        }
        trieTree node = root;
        trieTree tempNode;
        int len = key.length();
        for(int i = 0; i < len; ++i){
            tempNode = node->nodes[key[i] - 'a'];
            if(tempNode == nullptr){
                return v;
            }
            node = tempNode;
        }
        if(node->over){//如果查找到了返回
            v.push_back(node);
            return v;
        }
        //返回 以key为前缀的单词
        return fuzzySearch(node,v);
    }
    
    //判断是不是叶子节点
    bool isLeaf(trieTree node){
        for(int i = 0; i < 16; ++i){
            if(node->nodes[i] != nullptr){
                return false;
            }
        }
        return true;
    }

    //删除节点
    bool deleteNode(trieTree node,int nextSteps,string key,bool *ok){
        if(key == "" || key.size() == 0 || node == nullptr){
            return false;
        }

        int step = key.size();
        if(nextSteps == step){
            if(node->over){
                *ok = true;
                if(isLeaf(node)){//判断是删除单词还是节点
                    return true;
                }else{
                    node->over = false;
                    node->key = "";
                    node->value = "";
                    return false;
                }
            }else{
                return false;
            }
        }

        int pos = key[nextSteps] - 'a';
        if(pos > 25 || pos < 0){
            return false;
        }
        bool ok_delete = deleteNode(node->nodes[pos],nextSteps + 1,key,ok);
        if(ok_delete){
            trieTree p = node->nodes[pos];
            node->nodes[pos] = nullptr;
            delete(p);
            if(node->over){
                ok_delete = false;
            }
        }
        return ok_delete;
    }

    //删除单词
    bool deleteWord(string key){
        if(key.size() == 0 || key == ""){
            return false;
        }
        bool ok  = false;
        deleteNode(root->nodes[key[0] - 'a'],1,key,&ok);
        return ok;
    }
    
};
